/*
 * heap.c
 *
 *  Created on: 2020年2月20日
 *      Author: Administrator
 */



#include <stdio.h>
#include <stdlib.h>
#include "../../include/tree/heap.h"
#include "../../include/utils.h"

/**
 * 初始化堆
 * 使用数组表示堆
 */
void init_heap(Heap heap) {

	heap->data = (ElemType *)malloc(sizeof(ElemType) * MAX_SIZE);
	heap->size = 0;
}

bool is_full_heap(Heap heap) {
	if ( heap->size == MAX_SIZE ) {
		return true;
	}
	return false;
}

bool is_empty_heap(Heap heap) {

	if (heap->size == 0) {
		return true;
	}
	return false;
}

void create_heap(Heap heap, ElemType* array, int length) {

	if (heap == NULL) return;
	if (!is_empty_heap(heap)) return;

	// 插入元素
	for (int i = 0; i < length; ++i) {
		if (insert_heap(heap, array[i]) == false) {
			printf("插入错误！%d:%d\n", i, array[i]);
			return;
		}
	}
}

bool insert_heap(Heap heap, ElemType element) {

	if (is_full_heap(heap)) {
		return false;
	}

	// 在数组尾部添加元素
	heap->data[++heap->size] = element;

	// 调整heap
	int end = heap->size / 2;  // 调整起始
	// 自底向上调整策略
	for (int root = end; root >= 1; --root) {
		adjust_heap(heap, root, heap->size);  // 反复调整heap
	}
	return true;
}

void adjust_heap(Heap heap, int root, int end) {

	int child = root * 2;

	// 保证左子树孩子路径上的结点均满足堆结构
	while (child <= end) {

		if (child > heap->size) return;  // 左孩子不存在

		if (child+1 <= heap->size &&
					heap->data[child] > heap->data[child+1]) // 左右孩子比较，找小的
			child = child + 1;

		ElemType temp = heap->data[root];
		if (temp > heap->data[child]) {  // 小孩子比父节点比较，如果小孩子更小则交换

			heap->data[root] = heap->data[child]; // 交换
			heap->data[child] = temp;
		}
		root = root * 2;
		child = root * 2;
	}
}

/**
 * 出堆
 * 返回堆顶，尾元素为新堆顶，自顶向下调整堆
 * 细节：依次调整每层符合堆结构，父节点与两个孩子中较大的那个比较
 */
ElemType deheap(Heap heap) {

	ElemType result = -1;
	if (is_empty_heap(heap)) {
		printf("堆为空，不能出堆！");
		return result;
	}

	int top = 1;
	result = heap->data[top];  // 堆顶

	// 把最后一个元素作为根节点
	heap->data[top] = heap->data[heap->size];
	heap->data[heap->size] = INT_MAX;
	heap->size--;

	// 调整堆结构
	int end = heap->size / 2;  // 调整起始
	// 自底向上调整策略
	for (int root = end; root >= 1; --root) {
		adjust_heap(heap, root, heap->size);  // 反复调整heap
	}

	return result;
}

void heap_sort(Heap heap) {

	int length = heap->size;

	for (int i = length; i >= 1; --i) {
		int min = deheap(heap);
		printf("%d ", min);
	}
	printf("\n");
}

void print_heap(Heap heap) {

	int length = heap->size;

	for (int i = 1; i <= length; ++i) {
		printf("%d ", heap->data[i]);
	}
	printf("\n");
}
